%!TEX root = main.tex
\section{Introduction}
NDNS\cite{afanasyev2013addressing,shock:ndns} allows a specific zone contain multiple name server running simultaneously in the needs of
a) reliability: redundancy servers keep answering NDNS queries in case part of servers are down or disconnected from network;
b) performance: shorten the average distance from end consumers to name servers.

In order to keep consistency, the databases of those name servers belonging to a specific zone need to be synchronized,
especially when the following events:
\begin{itemize}
\item One specific name server receives a NDNS Update message
\item Administrator changes RR in a specific name server.
\end{itemize}

In this report, we propose a name server synchronization solution
which relies on ChronoSync\cite{zhu2013let} is a well-built decentralized dataset state synchronization method in NDN,

The ChronoSync-based solution is a fully distributed approach.
Even if the network is partitioned, nodes in every sperated partition is able to synchronize their database;
and after the network recovers, all the nodes could synchronize with each other based on their existing state.

Compared to database synchronization in traditional DNS, the most significant advantage is that,
our decentralized design removes both single point of failure and traffic concentration problems commonly associated with centralized implementations,
while traditional DNS highly relies on ``master'' zone file.

\section{Mechanism}
According to my understanding of current ChronoSync implementation by reading the code,
I infer some limitations when using ChronoSync to synchronize database in NDNS
\begin{enumerate}
\item Current ChronoSync implementation uses int64 only as sequence number to distinguish messages generated by user application;
  while NDNS uses timestamp-based version number in its data name.
\item Current ChronoSync implementation adopts mutable style stat management, which only allow new content change the stat, but not replace/remove existing content;
  while RR in NDNS's database is possible to be replaced/removed.
%\item Current ChronoSync implementation assume the participates produce different contents,
%  while every name server in NDNS maintains identical
\end{enumerate}
Note that the above limitations are based on my personal understanding,
and any feedbacks, comments or corrections are welcomed.

In order to cover the first limitation, a special mapping is needed to translate a sequence number at a specific name server to a name of RR in the database.
This mapping should be static, which implies that the pair does not change after restarting.

And two mechanisms are needed here.
The first mechanism is to synchronize stat, which is called ``Stat Channel''.
The second mechanism is to synchronize data, i.e., fetching the data that local application does not have yet.,
here we call it ``Data Channel''.
For simplicity, database synchronization is implemented as individual application,
instead of a feature embedded by name server daemon.
In this case, we do not have to change existing code, and compiling/debugging takes less time.
The sync application contains a ChronoSync instance which makes use of stat channel.

Sync application passes a callback function to ChronoSync,
 which is called when ChronoSync realizes there is update.
The callback function uses data channel to fetch latest content.


In order to cover the second limitation, name server also tracks the mapping between sequence number and RR
to marks the outdated RRs, and NACK is used to answer those Interests for outdated RRs.


\subsection{Naming}
Two naming schemas are designed for different channels.
We use two names used by zone /net/ndnsim as an example here.
The Figure \ref{fig:name-syn} shows a broadcast name used by zone /net/ndnsim to synchronize stat.
The second part of the name, i.e., /NDNS-SYN/ndn/netsim is constructed by the application tag ``NDNS-SYN'',
and the zone name ``/net/ndnsim''. The third part is the latest stat digest.
Instances of ChronoSync send this kind of Interest periodically to synchronize the stat.

The Figure \ref{fig:name-data} shows a name used by data channel.
The naming schema in NDNS cannot be used here directly,
since that naming does not distinguish different name servers.
The second part of this name is made of name server id ``ucla-1'' and application tag ``NDNS-SYN'',
``ucla-1'' probably represents a name server located at UCLA.
The third part is the sequence number, inferred from digest tree.
Sync application sends Interest with this name to fetch the data that itself does not have.

\begin{figure}[h] \label{fig:naming-db-sync}
\centering
\subfloat[An example of Stat Channel data name] {\label{fig:name-syn}
\includegraphics[width=0.8\textwidth]{figures/stat-channel.png}}

\subfloat[An example of Data Channel data name] {\label{fig:name-data}
\includegraphics[width=0.6\textwidth]{figures/data-channel.png}}
\caption{Naming example}
\end{figure}


\subsection{Data Format}
Stat Channel is implemented by ChronoSync independently, and its packet format is defined in ChronoSync too.

Data Channel data format is shown in Figure \ref{fig:sync-data}.
\begin{figure}[h]
  \begin{center}
    \includegraphics[width=4in]{figures/db-sync-data-packet.pdf}
    \caption{Data channel Data packet format}
    \label{fig:sync-data}
  \end{center}
\end{figure}

As we can see, a RR Data packet is encapsulated in the Data channel data.
And this packet is not signed by its producer,
but consumer side needs to validate the inner packet.
\section{Details to work it out}
\subsection{Database}
To implementing a stable mapping between sequence number and RR, a table, named ``sync\_seq'' is created.
\begin{table}[h]
\caption{Table sync\_seq Scheme} \label{tab:zones}
\begin{center}
\begin{tabular}{lcll}
\toprule[1.5pt]
Column & Data Type & Meaning & Constraint\\
\midrule[1pt]
id & uint64 & The sequence number & primary key, auto-increase\\
rrset\_id & uint64 & the manipulated rrset & \\
stale & boolean & whether the data is stale &\\
\bottomrule[1.5pt]
\end{tabular}
\end{center}
\end{table}%
The column stale is used to mark outdated data. For example, a sequence number x add a rrset whose id is y,
but sequence number y (y > x) replace the rrset with new data.
In this case, the outdated data is no longer valid, and the entry x in sync\_seq should either be deleted or mark as stale.

With this table, the initial stat digest could be easily calculated even after restarting from a clash.
%If also support NDNS administrator creates new name server by copy database of existing name server.

\subsection{Handle Update}
Sync application passes a callback function to ChronoSync,
which is called when ChronoSync realizes there is update.
For example, the name of new content is /net/ndnsim/ucla-1/NDNS-SYNC/20.
Data channel should send an Interest with this name,
and this Interest should be routed to corresponding name server (ucla-1).
If the entry with id 20 does not exist or is marked as stale,
the name server would send a NACK;
otherwise, answer the Interest the data stored in its database.
The process is shown in Figure \ref{fig:handle-sync-interest}
\begin{figure}[H]
  \begin{center}
    \includegraphics[width=4in]{figures/ns-handle-sync-interest.pdf}
    \caption{Name Server Handle Data channel Interest}
    \label{fig:handle-sync-interest}
  \end{center}
\end{figure}

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=4in]{figures/ns-handle-sync-data.pdf}
    \caption{Name Server Handle Data channel Data}
    \label{fig:handle-sync-data}
  \end{center}
\end{figure}

At the consumer side, the consumer drops the received packet if it is a NACK;
otherwise, consumer extracts the RR, validate the packet, and compares the version number,
As what it does when receiving an NDNS Update message.
The process is shown in Figure \ref{fig:handle-sync-data}.
